# -*- conding:utf-8 -*-
from algorithm.MGraph import MDWGraph
import numpy as np
import random
# import networkx as nx
# import matplotlib.pyplot as plt

from timeit import default_timer as timer

inf = 999999  # 边权无穷大


class NoConstrainsAlgorithm():
    # 输入例子的图
    def input_example_Graph(self):
        N = 14
        V = list(range(N))
        E = np.zeros((N, N))
        inf = 999
        E[0][1] = E[1][0] = E[3][5] = E[5][3] = E[5][12] = E[12][5] = E[5][6] = E[6][5] = E[6][4] = E[4][6] = E[3][2] = \
            E[2][3] = E[6][7] = E[7][6] = E[1][8] = E[8][1] = E[8][9] = E[9][8] = E[4][9] = E[9][4] = E[10][12] = E[12][
            10] = E[13][12] = E[12][13] = 1
        E[0][3] = E[3][0] = E[5][11] = E[11][5] = E[7][12] = E[12][7] = E[4][10] = E[4][10] = 2
        E[2][4] = E[4][2] = E[4][7] = E[7][4] = 3
        E[1][4] = E[4][1] = 4
        E[1][2] = E[2][1] = 6
        E[8][4] = E[4][8] = 6
        for i in range(len(E)):
            for j in range(len(E)):
                if i != j and E[i][j] == 0:
                    E[i][j] = E[j][i] = inf
        initial_Graph = MDWGraph(V, E)
        function_V = [2, 4, 7]

        return initial_Graph, function_V

    # 生成无向图
    def generate_NDGraph(self, V, E, destination, function_V):
        G = nx.Graph()
        color_map = []
        for i in V:
            if i in destination:
                color_map.append('green')
            elif i in function_V:
                color_map.append('red')
            else:
                color_map.append('blue')
            G.add_node(i)
        for i in range(len(E)):
            for j in range(i + 1, len(E)):
                if (E[i][j] != inf):
                    G.add_edge(i, j, weight=E[i][j], name=E[i][j], len=E[i][j])
        edge_labels = nx.get_edge_attributes(G, 'name')
        pos = nx.spring_layout(G)
        nx.draw(G, node_color=color_map, with_labels=True, pos=pos)
        nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)
        plt.show()

    # 生成无向图
    def generate_DGraph(self, V, E, function_V):
        G = nx.DiGraph()
        color_map = []
        for i in V:
            if i in range(len(V) - len(function_V), len(V)):
                color_map.append('red')
            else:
                color_map.append('green')
            G.add_node(i)
        edges = []
        for i in range(len(E)):
            for j in range(i + 1, len(E)):
                if (E[i][j] != inf):
                    edges.append((i, j))
        G.add_edges_from(edges)
        edge_labels = nx.get_edge_attributes(G, 'name')
        pos = nx.spring_layout(G)
        nx.draw(G, node_color=color_map, with_labels=True, pos=pos, cmap=plt.get_cmap('jet'))
        nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)
        plt.show()

    # 随机生成图：随机生成M个结点，连边概率p条边的图，为保证网络质量，每个结点至少有一条边与其他结点相连
    def random_initial_Graph(self, N, function_V_num, p, max_E_cost):
        V = list(range(N))
        E = np.zeros((N, N))
        for i in range(len(E)):
            for j in range(len(E)):
                if i != j and E[i][j] == 0:
                    E[i][j] = E[j][i] = inf
        # 随机产生边
        for i in range(N):
            flag = 0
            for j in range(N):
                if j == i:
                    continue
                prob = random.random()
                if prob < p:
                    flag = 1
                    Eij_cost = random.randint(1, max_E_cost)  # 随机产生边权
                    E[i][j] = E[j][i] = Eij_cost
            if flag == 0:
                j = random.randint(0, N - 1)  # 随机产生相连结点
                Eij_cost = random.randint(1, max_E_cost)  # 随机产生边权
                E[i][j] = E[j][i] = Eij_cost
        initial_Graph = MDWGraph(V, E)

        # 随机产生功能结点
        function_V = []
        for i in range(function_V_num):
            F_V = random.randint(0, N - 1)
            function_V.append(F_V)

        # 输出随机产生的图
        print('随机产生的结点个数：', initial_Graph.vnum)
        print('产生结点集合为：', initial_Graph.V)
        print('产生的边集合为：')
        print(initial_Graph.E)
        print('产生的功能结点分别是：', function_V)

        return initial_Graph, function_V

    # 输入原始的图
    def input_initial_Graph(self):
        N = 11
        V = list(range(N))
        E = np.zeros((N, N))
        inf = 999
        E[0][1] = E[1][0] = E[5][6] = E[6][5] = E[6][9] = E[9][6] = 1
        E[1][2] = E[2][1] = E[1][3] = E[3][1] = E[0][3] = E[3][0] = E[3][4] = E[4][3] = E[4][6] = E[6][4] = E[7][9] = \
            E[9][
                7] = 2
        E[2][3] = E[3][2] = E[2][4] = E[4][2] = E[4][7] = E[7][4] = E[5][8] = E[8][5] = 3
        E[7][10] = E[10][7] = E[2][5] = E[5][2] = 4
        for i in range(len(E)):
            for j in range(len(E)):
                if i != j and E[i][j] == 0:
                    E[i][j] = E[j][i] = inf
        initial_Graph = MDWGraph(V, E)
        function_V = [1, 2, 3, 4]

        return initial_Graph, function_V

    # 构造功能子图,调用返回功能子图
    def get_fuction_Graph(self, initial_Graph, function_V):
        dist = initial_Graph.floyd_warshall(1)
        # 求功能子图的边和结点
        N = len(function_V)  # 功能子图的结点数
        E = np.zeros((N, N))
        for i in range(N):
            for j in range(N):
                E[i][j] = E[j][i] = dist[function_V[i]][function_V[j]]
        fuction_Graph = MDWGraph(function_V, E)
        return fuction_Graph

    # 辅助功能
    def perm(self, arr):
        """实现全排列"""
        length = len(arr)
        if length == 1:  # 递归出口
            return [arr]

        result = []  # 存储结果
        fixed = arr[0]
        rest = arr[1:]

        for _arr in self.perm(rest):  # 遍历上层的每一个结果
            for i in range(0, length):  # 插入每一个位置得到新序列
                new_rest = _arr.copy()  # 需要复制一份
                new_rest.insert(i, fixed)
                result.append(new_rest)
        return result

    def factorial(self, x):
        """求阶乘"""
        if x == 0:
            return 1
        else:
            return x * self.factorial(x - 1)

    # 一行行输出大矩阵
    def printt(self, M):
        print('MOD图：')
        for i in range(len(M)):
            print('第', i, '行')
            print(M[i])

    # 处理并行功能长度超过4的情况
    def Auxiliary_Graph_to_multi_parallel(self, function_Graph, initial_Graph, request, function_V):
        parallel_num = request['parallel_num']
        parallel_position = request['parallel_position']
        function_num = request['function_num']
        deployment_cost = request['deployment_cost']
        bk = request['bk']
        source = request['source']
        dist, parent = initial_Graph.floyd_warshall()
        parallel_num_1 = 0
        parallel_num_2 = 0
        if parallel_num == 4:
            parallel_num_1 = 2
            parallel_num_2 = 2
        else:
            parallel_num_1 = 3
            parallel_num_2 = parallel_num - parallel_num_1
        parallel_position_1 = 0
        parallel_position_2 = function_num - parallel_num_2
        parallel_function_1 = list(range(parallel_position_1, parallel_position_1 + parallel_num_1))
        parallel_function_2 = list(range(parallel_position_2, parallel_position_2 + parallel_num_2))

        subGraph_num_1 = self.factorial(parallel_num_1)
        subGraph_num_2 = self.factorial(parallel_num_2)
        subGraph_num = subGraph_num_1 + subGraph_num_2

        function_list_1 = self.perm(parallel_function_1)
        function_list_2 = self.perm(parallel_function_2)
        # 构造辅助图
        parallel_portion_node_1 = subGraph_num_1 * (len(function_Graph.V)) * parallel_num_1  # 第一个并行部分的结点数
        not_parallel_portion_node = (len(function_Graph.V)) * (function_num - parallel_num)  # 非并行部分的结点数
        parallel_portion_node_2 = subGraph_num_2 * (len(function_Graph.V)) * parallel_num_2  # 第二个并行部分的结点数
        function_Vnum = 1 + parallel_portion_node_1 + not_parallel_portion_node + parallel_portion_node_2
        Auxiliary_Vnum = function_Vnum
        Auxiliary_V = list(range(Auxiliary_Vnum))
        last_V = {}
        dist_V = {}
        Auxiliary_E = np.zeros((Auxiliary_Vnum, Auxiliary_Vnum))
        for i in range(len(Auxiliary_E)):
            for j in range(len(Auxiliary_E)):
                if i != j and Auxiliary_E[i][j] == 0:
                    Auxiliary_E[i][j] = Auxiliary_E[j][i] = inf

        node_deploy_server = {}

        # 连接边
        # 连接源节点到第一列
        for i in range(subGraph_num_1):
            for j in range(len(function_V)):
                function = function_list_1[i][0]
                row = 0
                col = i * len(function_V) + j + 1
                node_deploy_server[col] = function
                Auxiliary_E[row][col] = Auxiliary_E[col][row] = dist[source][function_V[j]] * bk + \
                                                                deployment_cost[j][function]
                last_V[col] = row
                dist_V[col] = Auxiliary_E[row][col]

        # 连接并行结点
        for i in range(1, parallel_num_1):
            for j in range(subGraph_num_1):
                for k in range(len(function_V)):
                    function = function_list_1[j][i]
                    col = i * len(function_V) * subGraph_num_1 + j * len(function_V) + k + 1
                    node_deploy_server[col] = function
                    min_dist = inf
                    for a in range(len(function_V)):
                        row = (i - 1) * len(function_V) * subGraph_num_1 + j * len(function_V) + a + 1
                        min_d = deployment_cost[k][function] + dist_V[row] + dist[function_V[a]][
                            function_V[k]] * bk

                        if (min_d < min_dist):
                            min_dist = min_d
                            min_row = row
                            min_a = a
                    Auxiliary_E[min_row][col] = Auxiliary_E[col][min_row] = deployment_cost[k][function] + \
                                                                            dist[function_V[min_a]][
                                                                                function_V[k]] * bk
                    last_V[col] = min_row
                    dist_V[col] = min_dist
        # 连接并行与非并行结点
        for i in range(len(function_V)):
            col = subGraph_num_1 * len(function_V) * parallel_num_1 + 1 + i
            function = parallel_num_1
            node_deploy_server[col] = function
            min_dist = inf
            for k in range(subGraph_num_1 * len(function_V)):
                row = (parallel_num_1 - 1) * len(function_V) * subGraph_num_1 + k + 1
                min_d = dist[function_V[k % len(function_V)]][function_V[i]] * bk + deployment_cost[i][
                    function] + dist_V[row]
                if (min_d < min_dist):
                    min_dist = min_d
                    min_row = row
                    min_k = k
            Auxiliary_E[min_row][col] = Auxiliary_E[col][min_row] = \
                dist[function_V[min_k % len(function_V)]][
                    function_V[i]] * bk + \
                deployment_cost[i][function]
            last_V[col] = min_row
            dist_V[col] = min_dist

        # 连接非并行结点
        for i in range(parallel_num_1 + 1, parallel_position_2):
            function = i
            for j in range(len(function_V)):
                col = subGraph_num_1 * len(function_V) * parallel_num_1 + 1 + (i - parallel_num_1) * len(
                    function_V) + j
                node_deploy_server[col] = function
                min_dist = inf
                for k in range(len(function_V)):
                    row = subGraph_num_1 * len(function_V) * parallel_num_1 + 1 + (i - parallel_num_1 - 1) * len(
                        function_V) + k
                    min_d = dist[function_V[k]][function_V[j]] * bk + deployment_cost[j][function] + dist_V[row]
                    if (min_d < min_dist):
                        min_dist = min_d
                        min_row = row
                        min_k = k
                Auxiliary_E[min_row][col] = Auxiliary_E[col][min_row] = dist[function_V[min_k]][
                                                                            function_V[j]] * bk + \
                                                                        deployment_cost[j][
                                                                            function]
                last_V[col] = min_row
                dist_V[col] = min_dist

        # 连接非并行与并行
        for i in range(subGraph_num_2):
            for j in range(len(function_V)):
                function = function_list_2[i][0]
                col = parallel_portion_node_1 + not_parallel_portion_node + 1 + i * len(function_V) + j
                node_deploy_server[col] = function
                min_dist = inf
                for k in range(len(function_V)):
                    row = parallel_portion_node_1 + not_parallel_portion_node - len(function_V) + 1 + k
                    min_d = dist[function_V[k]][function_V[j]] * bk + deployment_cost[j][function] + dist_V[row]
                    if (min_d < min_dist):
                        min_dist = min_d
                        min_row = row
                        min_k = k
                Auxiliary_E[min_row][col] = Auxiliary_E[col][min_row] = dist[function_V[min_k]][
                                                                            function_V[j]] * bk + \
                                                                        deployment_cost[j][
                                                                            function]
                last_V[col] = min_row
                dist_V[col] = min_dist

        # 连接并行
        for i in range(parallel_position_2 + 1, parallel_position_2 + parallel_num_2):
            for j in range(subGraph_num_2):
                for k in range(len(function_V)):
                    function = function_list_2[j][i - parallel_position_2]
                    col = parallel_portion_node_1 + not_parallel_portion_node + (i - parallel_position_2) * len(
                        function_V) * subGraph_num_2 + j * len(function_V) + k + 1
                    node_deploy_server[col] = function
                    min_dist = inf
                    for a in range(len(function_V)):
                        row = parallel_portion_node_1 + not_parallel_portion_node + (i - parallel_position_2 - 1) * len(
                            function_V) * subGraph_num_2 + j * len(function_V) + a + 1
                        min_d = deployment_cost[k][function] + dist_V[row] + dist[function_V[a]][
                            function_V[k]] * bk
                        if (min_d < min_dist):
                            min_dist = min_d
                            min_row = row
                            min_a = a
                    Auxiliary_E[min_row][col] = Auxiliary_E[col][min_row] = deployment_cost[k][function] + \
                                                                            dist[function_V[min_a]][
                                                                                function_V[k]] * bk
                    last_V[col] = min_row
                    dist_V[col] = min_dist

        Auxiliary_Graph = MDWGraph(Auxiliary_V, Auxiliary_E)
        return Auxiliary_Graph, node_deploy_server

    def Auxiliary_Graph(self, function_Graph, initial_Graph, request, function_V):
        parallel_num = request['parallel_num']
        parallel_position = request['parallel_position']
        function_num = request['function_num']
        deployment_cost = request['deployment_cost']
        bk = request['bk']
        source = request['source']
        dist, parent = initial_Graph.floyd_warshall()
        parallel_function = list(range(parallel_position, parallel_position + parallel_num))
        subGraph_num = self.factorial(parallel_num)
        function_list = self.perm(parallel_function)

        # 构造辅助图
        parallel_portion_node = subGraph_num * (len(function_Graph.V)) * parallel_num  # 并行部分的结点数
        not_parallel_portion_node = (len(function_Graph.V)) * (function_num - parallel_num)  # 非并行部分的结点数
        function_Vnum = 1 + parallel_portion_node + not_parallel_portion_node
        Auxiliary_Vnum = function_Vnum
        Auxiliary_V = list(range(Auxiliary_Vnum))
        last_V = {}
        dist_V = {}
        Auxiliary_E = np.zeros((Auxiliary_Vnum, Auxiliary_Vnum))
        for i in range(len(Auxiliary_E)):
            for j in range(len(Auxiliary_E)):
                if i != j and Auxiliary_E[i][j] == 0:
                    Auxiliary_E[i][j] = Auxiliary_E[j][i] = inf

        node_deploy_server = {}
        functionDeployServerDic = []
        # 连接源节点到第一列
        if (parallel_position == 0):
            # 连接源节点到第一列
            for i in range(subGraph_num):
                for j in range(len(function_V)):
                    function = function_list[i][0]
                    row = 0
                    col = i * len(function_V) + j + 1
                    node_deploy_server[col] = function
                    Auxiliary_E[row][col] = Auxiliary_E[col][row] = dist[source][function_V[j]] * bk + \
                                                                    deployment_cost[j][function]
                    last_V[col] = row
                    dist_V[col] = Auxiliary_E[row][col]

            # 连接并行结点
            for i in range(1, parallel_num):
                for j in range(subGraph_num):
                    for k in range(len(function_V)):
                        function = function_list[j][i]
                        col = i * len(function_V) * subGraph_num + j * len(function_V) + k + 1
                        node_deploy_server[col] = function
                        min_dist = inf
                        for a in range(len(function_V)):
                            row = (i - 1) * len(function_V) * subGraph_num + j * len(function_V) + a + 1
                            min_d = deployment_cost[k][function] + dist_V[row] + dist[function_V[a]][
                                function_V[k]] * bk

                            if (min_d < min_dist):
                                min_dist = min_d
                                min_row = row
                                min_a = a
                        Auxiliary_E[min_row][col] = Auxiliary_E[col][min_row] = deployment_cost[k][function] + \
                                                                                dist[function_V[min_a]][
                                                                                    function_V[k]] * bk
                        last_V[col] = min_row
                        dist_V[col] = min_dist

            # 连接并行与非并行结点
            for i in range(len(function_V)):
                col = subGraph_num * len(function_V) * parallel_num + 1 + i
                function = parallel_num
                node_deploy_server[col] = function
                min_dist = inf
                for k in range(subGraph_num * len(function_V)):
                    row = (parallel_num - 1) * len(function_V) * subGraph_num + k + 1
                    min_d = dist[function_V[k % len(function_V)]][function_V[i]] * bk + deployment_cost[i][
                        function] + dist_V[row]
                    if (min_d < min_dist):
                        min_dist = min_d
                        min_row = row
                        min_k = k
                Auxiliary_E[min_row][col] = Auxiliary_E[col][min_row] = dist[function_V[min_k % len(function_V)]][
                                                                            function_V[i]] * bk + \
                                                                        deployment_cost[i][function]
                last_V[col] = min_row
                dist_V[col] = min_dist

            # 连接非并行结点
            for i in range(parallel_num + 1, function_num):
                function = i
                for j in range(len(function_V)):
                    col = subGraph_num * len(function_V) * parallel_num + 1 + (i - parallel_num) * len(
                        function_V) + j
                    node_deploy_server[col] = function
                    min_dist = inf
                    for k in range(len(function_V)):
                        row = subGraph_num * len(function_V) * parallel_num + 1 + (i - parallel_num - 1) * len(
                            function_V) + k
                        min_d = dist[function_V[k]][function_V[j]] * bk + deployment_cost[j][function] + dist_V[row]
                        if (min_d < min_dist):
                            min_dist = min_d
                            min_row = row
                            min_k = k
                    Auxiliary_E[min_row][col] = Auxiliary_E[col][min_row] = dist[function_V[min_k]][
                                                                                function_V[j]] * bk + \
                                                                            deployment_cost[j][
                                                                                function]
                    last_V[col] = min_row
                    dist_V[col] = min_dist
        else:
            # 连接源节点到第一列
            for i in range(len(function_V)):
                row = 0
                col = i + 1
                node_deploy_server[col] = 0
                Auxiliary_E[row][col] = Auxiliary_E[col][row] = dist[source][function_V[i]] * bk + \
                                                                deployment_cost[i][0]
                last_V[col] = row
                dist_V[col] = Auxiliary_E[row][col]

            # 连接非并行
            for i in range(1, parallel_position):
                for j in range(len(function_V)):
                    function = i
                    col = i * len(function_V) + 1 + j
                    node_deploy_server[col] = function
                    min_dist = inf
                    for k in range(len(function_V)):
                        row = (i - 1) * len(function_V) + 1 + k
                        min_d = dist[function_V[k]][function_V[j]] * bk + deployment_cost[j][function] + dist_V[row]
                        if (min_d < min_dist):
                            min_dist = min_d
                            min_row = row
                            min_k = k
                    Auxiliary_E[min_row][col] = Auxiliary_E[col][min_row] = dist[function_V[min_k]][
                                                                                function_V[j]] * bk + \
                                                                            deployment_cost[j][
                                                                                function]
                    last_V[col] = min_row
                    dist_V[col] = min_dist

            # 连接非并行与并行
            for i in range(subGraph_num):
                for j in range(len(function_V)):
                    function = function_list[i][0]
                    col = (i + parallel_position) * len(function_V) + 1 + j
                    node_deploy_server[col] = function
                    min_dist = inf
                    for k in range(len(function_V)):
                        row = (parallel_position - 1) * len(function_V) + 1 + k
                        min_d = dist[function_V[k]][function_V[j]] * bk + deployment_cost[j][function] + dist_V[row]
                        if (min_d < min_dist):
                            min_dist = min_d
                            min_row = row
                            min_k = k
                    Auxiliary_E[min_row][col] = Auxiliary_E[col][min_row] = dist[function_V[min_k]][
                                                                                function_V[j]] * bk + \
                                                                            deployment_cost[j][
                                                                                function]
                    last_V[col] = min_row
                    dist_V[col] = min_dist

            # 连接并行
            for i in range(parallel_position + 1, parallel_position + parallel_num):
                for j in range(subGraph_num):
                    for k in range(len(function_V)):
                        function = function_list[j][i - parallel_position]
                        col = parallel_position * len(function_V) + (i - parallel_position) * len(
                            function_V) * subGraph_num + j * len(function_V) + k + 1
                        node_deploy_server[col] = function
                        min_dist = inf
                        for a in range(len(function_V)):
                            row = parallel_position * len(function_V) + (i - parallel_position - 1) * len(
                                function_V) * subGraph_num + j * len(function_V) + a + 1
                            min_d = deployment_cost[k][function] + dist_V[row] + dist[function_V[a]][
                                function_V[k]] * bk
                            if (min_d < min_dist):
                                min_dist = min_d
                                min_row = row
                                min_a = a
                        Auxiliary_E[min_row][col] = Auxiliary_E[col][min_row] = deployment_cost[k][function] + \
                                                                                dist[function_V[min_a]][
                                                                                    function_V[k]] * bk
                        last_V[col] = min_row
                        dist_V[col] = min_dist

            # 连接并行与非并行结点
            if (parallel_position + parallel_num != function_num):
                for i in range(len(function_V)):
                    col = parallel_position * len(function_V) + subGraph_num * len(
                        function_V) * parallel_num + 1 + i
                    function = parallel_num + parallel_position
                    node_deploy_server[col] = function
                    for j in range(subGraph_num):
                        min_dist = inf
                        for k in range(len(function_V)):
                            row = parallel_position * len(function_V) + (parallel_num - 1) * len(
                                function_V) * subGraph_num + j * len(function_V) + k + 1
                            min_d = dist[function_V[k]][function_V[i]] * bk + deployment_cost[i][
                                function] + dist_V[row]
                            if (min_d < min_dist):
                                min_dist = min_d
                                min_row = row
                                min_k = k
                        Auxiliary_E[min_row][col] = Auxiliary_E[col][min_row] = dist[function_V[min_k]][
                                                                                    function_V[i]] * bk + \
                                                                                deployment_cost[i][function]
                        last_V[col] = min_row
                        dist_V[col] = min_dist

            # 连接非并行结点
            if (parallel_position + parallel_num < function_num - 1):
                for i in range(parallel_position + parallel_num + 1, function_num):
                    function = i
                    for j in range(len(function_V)):
                        col = parallel_position * len(function_V) + subGraph_num * len(function_V) * (
                                parallel_num - parallel_position) + 1 + (
                                      i - parallel_num - parallel_position) * len(function_V) + j
                        node_deploy_server[col] = function
                        min_dist = inf
                        for k in range(len(function_V)):
                            row = parallel_position * len(function_V) + subGraph_num * len(function_V) * (
                                    parallel_num - parallel_position - 1) + 1 + (
                                          i - parallel_num - 1 - parallel_position) * len(function_V) + k
                            min_d = dist[function_V[k]][function_V[j]] * bk + deployment_cost[j][function] + dist_V[
                                row]
                            if (min_d < min_dist):
                                min_dist = min_d
                                min_row = row
                                min_k = k
                        Auxiliary_E[min_row][col] = Auxiliary_E[col][min_row] = dist[function_V[min_k]][
                                                                                    function_V[j]] * bk + \
                                                                                deployment_cost[j][function]
                        last_V[col] = min_row
                        dist_V[col] = min_dist

        Auxiliary_Graph = MDWGraph(Auxiliary_V, Auxiliary_E)
        # self.generate_DGraph(Auxiliary_V, Auxiliary_E,function_V)
        return Auxiliary_Graph, node_deploy_server

    # 计算功能的部署结点
    def computeDeployV(self, function_V, function, dist, request, lastV):
        deployment_cost = request['deployment_cost']
        bk = request['bk']
        deployWeight = []
        for i in range(len(function_V)):
            deployWeight.append(deployment_cost[i][function] + dist[lastV][function_V[i]] * bk)
        minWeight = min(deployWeight)
        deployV = function_V[deployWeight.index(minWeight)]
        return minWeight, deployV

    # 计算Steiner树
    def get_steiner_tree(self, initial_Graph, function_V, destination, deploy_result, bk):
        # 构造新辅助图用于求Steiner树
        new_Vnum = initial_Graph.vnum + len(function_V) + 1
        new_V = list(range(new_Vnum))
        new_E = np.zeros((new_Vnum, new_Vnum))
        for i in range(new_Vnum):
            for j in range(i + 1, new_Vnum):
                if i < initial_Graph.vnum and j < initial_Graph.vnum:
                    new_E[i][j] = new_E[j][i] = initial_Graph.E[i][j] * bk
                else:
                    new_E[i][j] = new_E[j][i] = inf

        new_E[new_Vnum - 1][new_Vnum - 1] = 0
        for i in range(initial_Graph.vnum + 1, new_Vnum):
            for j in range(i, new_Vnum):
                if i == j:
                    new_E[i][j] = 0
                else:
                    new_E[i][j] = new_E[j][i] = inf

        for i in range(len(function_V)):
            col = new_Vnum - 1 - len(function_V) + i
            new_E[new_Vnum - 1][col] = new_E[col][new_Vnum - 1] = deploy_result[i]['weight']
            # new_E[col][function_V[i]] = 1
            # new_E[function_V[i]][col] = 1
            new_E[col][function_V[i]] = 0
            new_E[function_V[i]][col] = 0
        new_Auxiliary_Graph = MDWGraph(new_V, new_E)

        V_cost = np.ones(new_Auxiliary_Graph.vnum)
        for x in destination:
            V_cost[x] = 0
        V_cost[new_Vnum - 1] = 0
        Tnode, Tmatrix, Ttable = new_Auxiliary_Graph.node_weight_steiner_tree_3(V_cost)

        print('steiner树包含的结点：')
        print(Tnode)
        # print('树邻接矩阵：')
        # print(Tmatrix)
        print('树邻接表：')
        print(Ttable)

        weightsum = 0
        for i in range(len(new_Auxiliary_Graph.V)):
            for j in range(i, len(new_Auxiliary_Graph.V)):
                if Tmatrix[i][j] == 1:
                    weightsum = weightsum + new_Auxiliary_Graph.E[i][j]
        print('steiner树的总权值：')
        print(weightsum)

        # 求服务功能链
        SFC = deploy_result[0]
        for i in range(len(function_V)):
            if (Tmatrix[i + initial_Graph.vnum][new_Auxiliary_Graph.vnum - 1] == 1):
                SFC = deploy_result[i]
        print('SFC:', SFC)

        return Tmatrix, Ttable, weightsum, SFC

    # 处理单条请求
    def noContraintTackleRequest(self, request, parallel_num, initial_Graph, function_V):
        source = request['source']
        destination = request['destination']
        bk = request['bk']
        dist, parent = initial_Graph.floyd_warshall()
        function_Graph = self.get_fuction_Graph(initial_Graph, function_V)
        # self.generate_NDGraph(initial_Graph.V, initial_Graph.E, request['destination'], function_V)
        dijstradists = []
        primaryRoutes = []
        deploy_Nodes = []
        deploy_servers = []
        if request['parallel_num'] >= 4:
            Auxiliary_Graph, node_deploy_server = self.Auxiliary_Graph_to_multi_parallel(function_Graph, initial_Graph,
                                                                                         request, function_V)
            minroutes = Auxiliary_Graph.dijkstra(0)
            last_parallel_num = 0
            if parallel_num == 6:
                last_parallel_num = 3
            else:
                last_parallel_num = 2
            for a in range(last_parallel_num):
                for i in range(Auxiliary_Graph.vnum - (1 + a) * len(function_V),
                               Auxiliary_Graph.vnum - a * len(function_V)):
                    route = Auxiliary_Graph.dijkstra_route(minroutes, 0, i)
                    if route == 0 and len(dijstradists) < len(function_V):
                        dijstradists.append(inf)
                        primaryRoutes.append([])
                        deploy_Nodes.append([])
                        deploy_servers.append([])
                        continue
                    elif route == 0:
                        continue
                    primaryRoute, deploy_Node, deploy_server = self.convertToPrimary(route, source, function_V, parent,
                                                                                     node_deploy_server)
                    if len(dijstradists) < len(function_V):
                        dijstradists.append(minroutes[i]['dist'])
                        primaryRoutes.append(primaryRoute)
                        deploy_Nodes.append(deploy_Node)
                        deploy_servers.append(deploy_server)
                    if minroutes[i]['dist'] < dijstradists[(i - 1) % len(function_V)]:
                        dijstradists[(i - 1) % len(function_V)] = minroutes[i]['dist']
                        primaryRoutes[(i - 1) % len(function_V)] = primaryRoute
                        deploy_Nodes[(i - 1) % len(function_V)] = deploy_Node
                        deploy_servers[(i - 1) % len(function_V)] = deploy_server
        else:
            Auxiliary_Graph, node_deploy_server = self.Auxiliary_Graph(function_Graph, initial_Graph, request,
                                                                       function_V)

            # 求虚拟源节点到最后列结点的最短路径
            minroutes = Auxiliary_Graph.dijkstra(0)
            for i in range(Auxiliary_Graph.vnum - len(function_V), Auxiliary_Graph.vnum):
                route = Auxiliary_Graph.dijkstra_route(minroutes, 0, i)
                if route == 0:
                    dijstradists.append(inf)
                    primaryRoutes.append([])
                    deploy_Nodes.append([])
                    deploy_servers.append([])
                    continue
                primaryRoute, deploy_Node, deploy_server = self.convertToPrimary(route, source, function_V, parent,
                                                                                 node_deploy_server)
                dijstradists.append(minroutes[i]['dist'])
                primaryRoutes.append(primaryRoute)
                deploy_Nodes.append(deploy_Node)
                deploy_servers.append(deploy_server)
        # print(primaryRoutes)
        deploy_result = []
        for i in range(len(primaryRoutes)):
            deploy_in_i = {}
            deploy_in_i['weight'] = dijstradists[i]
            deploy_in_i['route'] = primaryRoutes[i]
            deploy_in_i['deploy_Node'] = deploy_Nodes[i]
            deploy_in_i['deploy_server'] = deploy_servers[i]
            deploy_result.append(deploy_in_i)
        # print(deploy_result)
        Tmatrix, Ttable, weightsum, SFC = self.get_steiner_tree(initial_Graph, function_V, destination, deploy_result,
                                                                bk)
        # Tmatrix, weightsum, SFC = self.optimize1(request, SFC, Tmatrix, Ttable, weightsum, function_V, dist, parent,
        #                                          destination)
        # Tmatrix, weightsum, SFC = self.optimize2(request, SFC, Tmatrix, Ttable, weightsum, function_V, dist, parent,
        #                                          destination)
        # Tmatrix, weightsum, SFC = self.optimize3(request, SFC, Tmatrix, Ttable, weightsum, function_V, initial_Graph,
        #                                          destination)

        # 返回树
        T = np.zeros((initial_Graph.vnum, initial_Graph.vnum))
        deployRoute = SFC['route']
        for i in range(1, len(deployRoute)):
            if (deployRoute[i - 1] != deployRoute[i]):
                T[deployRoute[i - 1]][deployRoute[i]] = T[deployRoute[i]][deployRoute[i - 1]] = 1
        for i in range(initial_Graph.vnum):
            for j in range(i, initial_Graph.vnum):
                if T[i][j] == 0:
                    T[i][j] = T[j][i] = Tmatrix[i][j]

        return Tmatrix, Ttable, weightsum, SFC, T

    # 将Mod图的最短路径转化为原始图路径
    def convertToPrimary(self, route, source, function_V, parent, node_deploy_server):
        route2 = np.zeros(len(route))
        deployNode = []
        deploy_server = []
        for i in range(len(route)):
            if i == 0:
                route2[i] = source
            else:
                route2[i] = function_V[(route[i] - 1) % len(function_V)]
            if i != 0:
                deployNode.append(int(route2[i]))
                deploy_server.append(node_deploy_server[route[i]])

        primaryRoute = []

        pre_v = int(route2[0])
        primaryRoute.append(pre_v)
        for i in range(1, len(route2)):
            v = int(route2[i])
            v_pre = v
            a = len(primaryRoute)
            while True:
                primaryRoute.insert(a, v)
                v = int(parent[v][pre_v])
                if v == pre_v:
                    break
            pre_v = v_pre
        return primaryRoute, deployNode, deploy_server

    # 处理单条请求
    # def noContraintTackleRequest(self, request, parallel_num, initial_Graph, function_V):
    #     function_Graph = self.get_fuction_Graph(initial_Graph, function_V)
    #     self.generate_NDGraph(initial_Graph.V, initial_Graph.E, request['destination'], function_V)
    #     Auxiliary_Graph = self.Auxiliary_Graph(function_Graph, initial_Graph, request, function_V)
    #
    #     # steiner tree计算结果
    #     new_destination = []
    #     destination = request['destination']
    #     function_Vnum = Auxiliary_Graph.vnum - initial_Graph.vnum
    #     for v in destination:
    #         new_destination.append(v + function_Vnum)
    #     V_cost = np.ones(Auxiliary_Graph.vnum)
    #     for x in new_destination:
    #         V_cost[x] = 0
    #     V_cost[0] = 0
    #     Tnode, Tmatrix, Ttable = Auxiliary_Graph.node_weight_steiner_tree_3(V_cost)
    #     print("*****************************计算结果*****************************")
    #     weightsum = 0
    #     for i in range(len(Auxiliary_Graph.V)):
    #         for j in range(i + 1, len(Auxiliary_Graph.V)):
    #             if Tmatrix[i][j] == 1:
    #                 weightsum = weightsum + Auxiliary_Graph.E[i][j]
    #                 # print(i)
    #                 # print(j)
    #                 # print(Auxiliary_Graph.E[i][j])
    #     print('最终结果总权值为：', weightsum)
    #     print(Ttable)

    # 求某结点到目的节点的路径
    def getToDestinationRoute(self, T, v, destination, route, routes, vnum, visit):
        if v in destination:
            routes.append(route.copy())
            return
        for i in range(vnum):
            if (visit[i] == 0 and T[v][i] == 1):
                visit[i] = 1
                route.append(i)
                self.getToDestinationRoute(T, i, destination, route, routes, vnum, visit)
                visit[i] = 0
                route.remove(i)

    # 根据父矩阵获取路径
    def get_route(self, parent, source, destination):
        v = int(source)
        route = []
        while True:
            route.append(v)
            v = int(parent[v][destination])
            if v == destination:
                route.append(v)
                break

        return route

    # 优化一：将全部部署在同一结点的功能分出去。
    def optimize1(self, request, SFC, Tmatrix, Ttable, weightsum, function_V, dist, parent, destination):
        print("********************************* 优化一 **********************************")
        deploy_Node = SFC['deploy_Node']
        deploy_server = SFC['deploy_server']
        deployment_cost = request['deployment_cost']
        bk = request['bk']
        if (sum(deploy_Node) == len(deploy_Node) * deploy_Node[0]):
            deploy_V = deploy_Node[0]
            routes = []
            route = []
            route.append(deploy_V)
            visit = np.zeros(len(Tmatrix))
            visit[deploy_Node[0]] = 1
            self.getToDestinationRoute(Tmatrix, deploy_V, destination, route, routes,
                                       len(Tmatrix) - len(function_V) - 1, visit)
            # print('routes', routes)
            # 计算新路权值
            mindist = 0
            function_v_to_destinations = []
            for route in routes:
                mindi = inf
                min_function_v_i = -1
                function_v_to_destination = {'destination': route[-1]}
                for i in range(len(function_V)):
                    di = dist[deploy_V][function_V[i]] * bk + dist[function_V[i]][route[-1]] * bk + deployment_cost[i][
                        deploy_server[-1]]
                    if (di < mindi):
                        mindi = di
                        min_function_v_i = i
                function_v_to_destination['function_v'] = function_V[min_function_v_i]
                function_v_to_destinations.append(function_v_to_destination)
                mindist += mindi
            # print('mindist', mindist)

            # 计算旧路权值
            oldWeight = 0
            for route in routes:
                for i in range(len(route) - 1):
                    oldWeight += dist[route[i]][route[i + 1]] * bk
            oldWeight += deployment_cost[function_V.index(deploy_V)][deploy_server[-1]]

            # mindist = 1  # 临时测试
            if (oldWeight < mindist):
                print("优化一不修改旧结果！,oleWeight=", oldWeight)
            else:
                weightsum = weightsum - oldWeight + mindist
                for route in routes:
                    for i in range(len(route) - 1):
                        Tmatrix[route[i]][route[i + 1]] = Tmatrix[route[i + 1]][route[i]] = 0
                # 构造新的T
                new_function_v = []
                for function_v_to_destination in function_v_to_destinations:
                    function_v = function_v_to_destination['function_v']
                    new_function_v.append(function_v)
                    desti = function_v_to_destination['destination']
                    route1 = self.get_route(parent, deploy_V, function_v)
                    route2 = self.get_route(parent, function_v, desti)
                    for i in range(len(route1) - 1):
                        if (route1[i] != route1[i + 1]):
                            Tmatrix[route1[i]][route1[i + 1]] = Tmatrix[route1[i + 1]][route1[i]] = 1
                    for i in range(len(route2) - 1):
                        if (route2[i] != route2[i + 1]):
                            Tmatrix[route2[i]][route2[i + 1]] = Tmatrix[route2[i + 1]][route2[i]] = 1
                deploy_Node.pop()
                deploy_Node.append(new_function_v)
                print(deploy_Node)
                print(SFC['deploy_Node'])

        return Tmatrix, weightsum, SFC

    # 优化一：分化最后的功能成服务功能树，最后两功能并行时考虑调换功能顺序。
    def optimize2(self, request, SFC, Tmatrix, Ttable, weightsum, function_V, dist, parent, destination):
        print("********************************* 优化二 **********************************")
        deploy_Node = SFC['deploy_Node']
        deploy_server = SFC['deploy_server']
        deployment_cost = request['deployment_cost']
        bk = request['bk']
        parallel_position = request['parallel_position']
        parallel_num = request['parallel_num']
        function_num = request['function_num']
        # if len(set(deploy_Node)) == 1:# 临时测试
        if len(set(deploy_Node)) > 1 and parallel_position + parallel_num == function_num:
            deploy_V = deploy_Node[-2]
            route_to_destination = []
            route_to_destinations = []
            visit = np.zeros(len(Tmatrix))
            visit[deploy_Node[-2]] = 1
            self.getToDestinationRoute(Tmatrix, deploy_V, destination, route_to_destination, route_to_destinations,
                                       len(Tmatrix) - len(function_V) - 1, visit)

            # 计算新路权值
            mindist = 0
            function_v_to_destinations = []
            for route in route_to_destinations:
                mindi = inf
                min_function_v_i = -1
                function_v_to_destination = {'destination': route[-1]}
                for i in range(len(function_V)):
                    di = dist[deploy_V][function_V[i]] * bk + dist[function_V[i]][route[-1]] * bk + deployment_cost[i][
                        deploy_server[-2]]
                    if (di < mindi):
                        mindi = di
                        min_function_v_i = i
                function_v_to_destination['function_v'] = function_V[min_function_v_i]
                function_v_to_destinations.append(function_v_to_destination)
                mindist += mindi
            mindist += deployment_cost[function_V.index(deploy_V)][deploy_server[-1]]

            # 计算旧路权值

            route1 = self.get_route(parent, deploy_V, deploy_Node[-1])
            oldWeight = 0
            for i in range(len(route1) - 1):
                oldWeight += dist[route1[i]][route1[i + 1]] * bk
            route = []
            routes = []
            visit = np.zeros(len(Tmatrix))
            visit[deploy_Node[-1]] = 1
            self.getToDestinationRoute(Tmatrix, deploy_Node[-1], destination, route, routes,
                                       len(Tmatrix) - len(function_V) - 1, visit)
            for route in routes:
                for i in range(len(route) - 1):
                    oldWeight += dist[route[i]][route[i + 1]] * bk
            oldWeight += deployment_cost[function_V.index(deploy_V)][deploy_server[-2]]
            oldWeight += deployment_cost[function_V.index(deploy_Node[-1])][deploy_server[-1]]

            # 调整树
            if (oldWeight < mindist):
                print("优化二不修改旧结果！,oleWeight=", oldWeight)
            else:
                weightsum = weightsum - oldWeight + mindist
                # 删除最后功能点到目的点的边
                for route in routes:
                    for i in range(len(route) - 1):
                        Tmatrix[route[i]][route[i + 1]] = Tmatrix[route[i + 1]][route[i]] = 0
                # 删除倒数第二功能点到倒数第一点的边
                for i in range(len(route1) - 1):
                    oldWeight += dist[route1[i]][route1[i + 1]] * bk

                # 构造新的T
                new_function_v = []
                for function_v_to_destination in function_v_to_destinations:
                    function_v = function_v_to_destination['function_v']
                    new_function_v.append(function_v)
                    desti = function_v_to_destination['destination']
                    route1 = self.get_route(parent, deploy_V, function_v)
                    route2 = self.get_route(parent, function_v, desti)
                    for i in range(len(route1) - 1):
                        if (route1[i] != route1[i + 1]):
                            Tmatrix[route1[i]][route1[i + 1]] = Tmatrix[route1[i + 1]][route1[i]] = 1
                    for i in range(len(route2) - 1):
                        if (route2[i] != route2[i + 1]):
                            Tmatrix[route2[i]][route2[i + 1]] = Tmatrix[route2[i + 1]][route2[i]] = 1
                deploy_Node.pop()
                deploy_Node.append(new_function_v)
                temp = deploy_server[-1]
                deploy_server[-1] = deploy_server[-2]
                deploy_server[-2] = temp
                print(deploy_Node)
                print(SFC['deploy_Node'])
                print(SFC)
        else:
            print('无需优化！')

        return Tmatrix, weightsum, SFC

    # 优化三：处理掉回路
    def optimize3(self, request, SFC, Tmatrix, Ttable, weightsum, function_V, initial_Graph, destination):
        print("********************************* 优化三 **********************************")
        deploy_route = SFC['route']
        # print(deploy_route)
        deploy_Node = SFC['deploy_Node']
        source = request['source']
        bk = request['bk']
        new_E = np.array(initial_Graph.E)
        pre_v = deploy_route[0]
        hasCircle = False
        for i in range(1, len(deploy_route)):
            v = deploy_route[i]
            if Tmatrix[pre_v][v] == 1:
                hasCircle = True
                new_E[pre_v][v] = new_E[v][pre_v] = inf
            pre_v = v
        if hasCircle:
            new_Graph = MDWGraph(initial_Graph.V, new_E)
            dist, parent = new_Graph.floyd_warshall(0)

            source_to_deploy_node = self.get_route(parent, source, deploy_Node[0])

            between_deploy_nodes = []
            isVisit = []
            for i in range(1, len(deploy_Node)):
                if deploy_Node[i] not in isVisit:
                    between_deploy_nodes.append(self.get_route(parent, deploy_Node[i - 1], deploy_Node[i]))
                    isVisit.append(deploy_Node[i])
            new_deploy_route = []
            for v in source_to_deploy_node:
                new_deploy_route.append(v)
            for route in between_deploy_nodes:
                for i in range(1, len(route)):
                    new_deploy_route.append(route[i])
            # print(new_deploy_route)

            for i in range(1, len(deploy_route)):
                weightsum -= initial_Graph.E[deploy_route[i - 1]][deploy_route[i]] * bk
                SFC['weight'] -= initial_Graph.E[deploy_route[i - 1]][deploy_route[i]] * bk
            for i in range(1, len(new_deploy_route)):
                weightsum += initial_Graph.E[new_deploy_route[i - 1]][new_deploy_route[i]] * bk
                SFC['weight'] += initial_Graph.E[new_deploy_route[i - 1]][new_deploy_route[i]] * bk
            # print(weightsum)
            SFC['deploy_Node'] = new_deploy_route
            print(SFC)

        return Tmatrix, weightsum, SFC

# --------------------测试--------------------------------#
# deployment_cost = [[20, 40, 30, 40, 20,20], [20, 40, 40, 30, 30,50], [30, 30, 30, 20, 40,30], [20, 30, 20, 30, 25,40]]
# # deployment_cost = [[24, 24, 18, 15], [21, 18, 24, 18], [15, 21, 18, 21]]
# sk = {'source': 0, 'SFC': [1, 2, 3, 4], 'destination': [8, 9, 10], 'bk': 3, 'deployment_cost': deployment_cost,
#       'parallel_num': 4, 'parallel_position': 0, 'function_num': 6}
# # sk = {'source': 1, 'SFC': [1, 2, 3, 4], 'destination': [8, 6, 10, 13, 12], 'bk': 2, 'deployment_cost': deployment_cost,
# #       'parallel_num': 2, 'parallel_position': 0, 'function_num': 4}
# NCA = NoConstrainsAlgorithm()
# initial_Graph, function_V = NCA.input_initial_Graph()
# NCA.noContraintTackleRequest(sk, sk['parallel_num'], initial_Graph, function_V)

# request = {'source': 5, 'SFC': [1, 2, 3, 4, 5, 6], 'destination': [7, 2, 3], 'bk': 8,
#            'deployment_cost': [[699., 13., 18., 2., 15., 8.],
#                                [8., 3., 699., 699., 699., 2.],
#                                [699., 699., 699., 17., 699., 699.],
#                                [4., 5., 10., 6., 10., 10.]], 'parallel_num': 3,'parallel_position':0,'function_num':6}
#
# N = 10
# V = list(range(N))
# E = np.zeros((N, N))
# inf = 999
# E[0][8] = E[8][0] = E[6][9] = E[9][6] = 3
# E[2][5] = E[5][2] = E[3][9] = E[9][3] = E[4][7] = E[7][4] = 2
# E[2][7] = E[7][2] = 4
# E[2][4] = E[4][2] = 6
# E[3][8] = E[8][3] = 7
# E[1][7] = E[7][1] = 9
# E[1][3] = E[3][1] = 10
# for i in range(len(E)):
#     for j in range(len(E)):
#         if i != j and E[i][j] == 0:
#             E[i][j] = E[j][i] = inf
# initial_Graph = MDWGraph(V, E)
# function_V = [6,8,9,0]
# NCA = NoConstrainsAlgorithm()
# NCA.noContraintTackleRequest(request, request['parallel_num'], initial_Graph, function_V)
